# @Time: 2022/3/24 9:49
# @Author: HeYuanqing
# @Reference: https://wrf.ecse.rpi.edu//Research/Short_Notes/pnpoly.html


def Point_Polygon(vertices, point):  # vertices:多边形的顶点[[x1,y1],[x2,y3],...] point：判断点[x,y]
    vertN = len(vertices)
    j = vertN - 1
    c = 0
    testx = point[0]
    testy = point[1]
    for i in range(vertN):
        vertXi = vertices[i][0]
        vertYi = vertices[i][1]
        vertXj = vertices[j][0]
        vertYj = vertices[j][1]

        if (vertYi > testy) != (vertYj > testy):
            if testx < ((vertXj - vertXi) * (testy - vertYi) / (vertYj - vertYi) + vertXi):
                c = c + 1
        j = i
    if c % 2 == 0:
        return False
    else:
        return True


if __name__ == '__main__':
    # 示例
    # polygon = [[-0.8, 0.8], [-0.6, 0.9], [-0.6, 1.1], [-0.2, 1.2], [-0.3, 1], [-0.1, 0.9], [-0.3, 0.7], [-0.4, 0.9],
    #            [-0.5, 0.8]]
    polygon = [[0, 0], [1, 0], [1, 1], [0, 1]]
    testPoint = [-0.45, 0.95]
    result = Point_Polygon(polygon, testPoint)
    if result:
        print("点在多边形内")
    else:
        print("点在多边形外")

